package com.future;

import com.future.util.TreeNode;

import java.lang.*;
import java.util.*;

/**
 * Description: 236. �������������������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/25 17:42
 */
public class Solution_236 {

    /**
     * key-child
     * val-parent
     * Ŀ���Ǹ���child��ȡ��
     */
    private Map<Integer, TreeNode> childParent = new HashMap<>();
    /**
     * ��¼���ʹ��Ľڵ�ֵ
     * �׶ˣ�����ڵ�ֵ���ظ�������Ҫ��Integer->TreeNode
     */
    private Set<Integer> visited = new HashSet<>();

    /**
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            // ��¼������·��
            visited.add(p.val);
            p = childParent.get(p.val);
        }
        while (q != null) {
            // ���ظ�����ֱ�ӷ���
            if (!visited.add(q.val)) {
                return q;
            }
            q = childParent.get(q.val);
        }
        return null;
    }

    /**
     * ������-���Ĺ�ϵӳ��
     *
     * @param root
     */
    private void dfs(TreeNode root) {
        if (root.left != null) {
            childParent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            childParent.put(root.right.val, root);
            dfs(root.right);
        }
    }
}
